package com.test.daily.leetcode.y2022.m07.day0728.v02;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/28 上午 11:35
 * @version: 1.0
 */
public class Solution {
    // 1~N N个位置
    // M 机器人刚开始是在位置
    // K 机器人必须走K步
    // P 机器人到达P 位置的方法数
    public static int way1(int N, int M, int K, int P) {
        return process1(N, M, K, P);
    }

    // N 1~N个位置,
    // start 当前位置
    // rest 还剩下多少步要走
    // P 必须要到P才可以
    public static int process1(int N, int start, int rest, int P) {
        if (rest == 0) {
            return start == P ? 1 : 0;
        }
        if (start == 1) {
            return process1(N, 2, rest - 1, P);
        }
        if (start == N) {
            return process1(N, N - 1, rest - 1, P);
        }
        return process1(N, start + 1, rest - 1, P) + process1(N, start - 1, rest - 1, P);
    }

    // 1~N N个位置
    // M 机器人刚开始是在位置
    // K 机器人必须走K步
    // P 机器人到达P 位置的方法数
    public static int way2(int N, int M, int K, int P) {
        int[][] dp = new int[N + 1][K + 1];
        for (int i = 0; i < N + 1; i++) {
            for (int j = 0; j < K + 1; j++) {
                dp[i][j] = -1;
            }
        }
        return process2(N, M, K, P, dp);
    }

    // N 1~N个位置,
    // start 当前位置
    // rest 还剩下多少步要走
    // P 必须要到P才可以
    public static int process2(int N, int start, int rest, int P, int[][] dp) {
        if (dp[start][rest] != -1) {
            return dp[start][rest];
        } else if (rest == 0) {
            dp[start][rest] = start == P ? 1 : 0;
        } else if (start == 1) {
            dp[start][rest] = process2(N, 2, rest - 1, P, dp);
        } else if (start == N) {
            dp[start][rest] = process2(N, N - 1, rest - 1, P, dp);
        } else {
            dp[start][rest] = process2(N, start + 1, rest - 1, P, dp) + process2(N, start - 1, rest - 1, P, dp);
        }
        return dp[start][rest];
    }

    // 1~N N个位置
    // M 机器人刚开始是在位置
    // K 机器人必须走K步
    // P 机器人到达P 位置的方法数
    public static int way3(int N, int M, int K, int P) {
        int[][] dp = new int[N + 1][K + 1];
        dp[P][0] = 1;
        //
        for (int rest = 1; rest < K + 1; rest++) {
            dp[1][rest] = dp[2][rest - 1];
            for (int start = 1; start < K + 1; start++) {
                dp[start][rest] = dp[start + 1][rest - 1] + dp[start + 1][rest - 1];
            }
            dp[K][rest] = dp[K - 1][rest - 1];
        }
        return dp[M][K];
    }

}













